import java.util.HashMap;

/**
 * Created with IntelliJ IDEA.
 * Description: 优选算法：前缀和
 * User: 姚东名
 * Date: 2025-03-02
 * Time: 8:50
 */
public class Demo1 {
    // 1. 和为 K 的子数组
    public int subarraySum(int[] nums, int k) {
        // 准备一个哈希表
        HashMap<Integer, Integer> prefixSumCount = new HashMap<>();
        prefixSumCount.put(0, 1); // 表示 前缀和 0 出现了一次

        int count = 0; //
        int currentSum = 0; // 当前数组之和

        for (int num : nums) {
            currentSum += num; // 计算当前数组之和
            // 如果我们之前在某个位置 i 处，有一个前缀和为 currentSum - k ，
            // 那么这意味着从 i + 1 位置到 j 位置的子数组的和就正好是 k 。
            if (prefixSumCount.containsKey(currentSum - k)) {
                count += prefixSumCount.get(currentSum - k);
            }

            // 把当前前缀和 写入哈希表中
            prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) + 1);
        }

        return count;
    }

    public int subarraysDivByK(int[] nums, int k) {
        // 申请一个哈希表，记录前缀和的余数
        HashMap<Integer, Integer> remainderCount = new HashMap<>();
        // 理论上出现余数为 0 的 为 1 次
        remainderCount.put(0, 1);

        int prefixSum = 0; // 前缀和
        int count = 0; // 符合长度的前缀和子数组

        for (int num : nums) {
            prefixSum += num;

            // 负数 % 正数的结果以及修正: (num % k + k) % k
            // 计算正确的余数，将负号改正

            // 如果之前出现过相同的余数，说明找到了和能被k整除的子数组
            int remainder = (prefixSum % k + k) % k;
            if (remainderCount.containsKey(remainder)) {
                count += remainderCount.get(remainder);
            }

            // 更新相同余数出现的次数
            remainderCount.put(remainder, remainderCount.getOrDefault(remainder, 0) + 1);
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println("hello world");
        System.out.println("hello world");
    }
}

class Solution1 {
    public int findMaxLength(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>(); // 存放前缀和子数组 及其 坐标
        map.put(0, -1); // 初始化前缀和为0的位置为-1

        int maxLength = 0;
        int count = 0; // 前缀和

        for(int i = 0; i < nums.length; i++) {
            // 将0视为-1，1保持不变
            // count += (nums[i] == 0) ? -1 : 1;
            count += (nums[i] == 0) ? -1 : 1;
            // 当两个位置有相同的前缀和时，意味着这两个位置之间的子数组和为0，即子数组中0和1的数量相等。
            // 通过存储前缀和及其位置，我们可以快速找到符合条件的子数组。
            if (map.containsKey(count)) {
                // 求出最大长度
                // maxLength = Math.max(maxLength, i - map.get(count));
                maxLength = Math.max(maxLength, i - map.get(count));
            } else {
                // 记录该前缀和出现最早的位置
                map.put(count, i);
            }
        }
        return maxLength;
    }
}
